﻿//大数乘法
// 不明确问题
//class Solution
//{
//public:
//    string solve(string s, string t)
//    {
//        if (s.empty())
//        {
//            return t;
//        }
//        if (t.empty())
//        {
//            return s;
//        }
//        if (s == "0" || t == "0")
//        {
//            return "0";
//        }
//        string str(t);
//        string sp(s.size(), '0');
//        sp[s.size() - 1] = '1';
//        while (sp != s)
//        {
//            if (s[s.size() - 1] == '0')
//            {
//                int i = s.size() - 2;
//                while (s[i] == '0')
//                {
//                    s[i] = '9';
//                    i--;
//                }
//                s[i] -= 1;
//                s[s.size() - 1] = '9' + 1;
//            }
//            //str与t加法操作
//            int x = 0; //进位数
//            for (int i = 1; i <= t.size(); i++)
//            {
//                str[str.size() - i] += x + t[t.size() - i] - 48;
//                if (str[str.size() - i] > '9')
//                {
//                    str[str.size() - i] -= 10;
//                    x = 1;
//                }
//                else
//                {
//                    x = 0;
//                }
//            }
//            if (x == 1)
//            {
//                for (int i = str.size() - t.size() - 1; i >= 0; i--)
//                {
//                    if (str[i] + x > '9')
//                    {
//                        str[i] = '0';
//                        x = 1;
//                    }
//                    else
//                    {
//                        str[i] += x;
//                        x = 0;
//                        break;
//                    }
//                }
//                if (x == 1)
//                {
//                    str.insert(str.begin(), '1');
//                }
//            }
//            s[s.size() - 1] -= 1;
//        }
//        return str;
//    }
//};


//岛屿数量
//错误
//#include <iostream>
//#include <string>
//#include <map>
//using namespace std;
//int main()
//{
//    string str;
//    map<int, string> m;
//    cin >> str;
//    for (int i = 0; i < str.size(); i++)
//    {
//        int count = 0;
//        string s;
//        while (str[i] >= '0' && str[i] <= '9')
//        {
//            count++;
//            s.push_back(str[i]);
//            i++;
//        }
//        if (count)
//        {
//            m[count] = s;
//        }
//    }
//    int max = 0;
//    for (map<int, string>::iterator it = m.begin(); it != m.end(); it++)
//    {
//        if (it->first > max)
//        {
//            max = it->first;
//        }
//    }
//    cout << m[max] << endl;
//    return 0;
//}



//字母收集
////错误方法
//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//int main()
//{
//    int n = 0, m = 0;
//    int count = 0;
//    cin >> n >> m;
//    vector<string> v(n);
//    for (int i = 0; i < n; i++) {
//        v[i].resize(m);
//        cin >> v[i];
//    }
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            if (i == n - 1 && j == m - 1)
//            {
//                break;
//            }
//            while (i == n - 1 && j < m) {
//                if (v[i][j] == 'l') {
//                    count += 4;
//                }
//                else if (v[i][j] == 'o') {
//                    count += 3;
//                }
//                else if (v[i][j] == 'v') {
//                    count += 2;
//                }
//                else if (v[i][j] == 'e') {
//                    count += 1;
//                }
//                j++;
//            }
//            while (i < n && j == m - 1) {
//                if (v[i][j] == 'l') {
//                    count += 4;
//                }
//                else if (v[i][j] == 'o') {
//                    count += 3;
//                }
//                else if (v[i][j] == 'v') {
//                    count += 2;
//                }
//                else if (v[i][j] == 'e') {
//                    count += 1;
//                }
//                i++;
//            }
//
//        }
//    }
//    cout << count << endl;
//    return 0;
//}
////正确方法
//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//int main() {
//    int n, m;
//    cin >> n >> m;
//    vector<char> stemp(m);
//    vector<vector<char>> arr(n, stemp);
//    vector<int> itemp(m, 0);
//    vector<vector<int>> sum(n, itemp);
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            cin >> arr.at(i).at(j);
//            if (arr.at(i).at(j) == 'l') {
//                sum.at(i).at(j) = 4;
//            }
//            else if (arr.at(i).at(j) == 'o') {
//                sum.at(i).at(j) = 3;
//            }
//            else if (arr.at(i).at(j) == 'v') {
//                sum.at(i).at(j) = 2;
//            }
//            else if (arr.at(i).at(j) == 'e') {
//                sum.at(i).at(j) = 1;
//            }
//            if (i == 0 && j != 0) {
//                sum.at(i).at(j) += sum.at(i).at(j - 1);
//            }
//            else if (i != 0 && j == 0) {
//                sum.at(i).at(j) += sum.at(i - 1).at(j);
//            }
//            else if (i != 0 && j != 0) {
//                sum.at(i).at(j) += max(sum.at(i).at(j - 1), sum.at(i - 1).at(j));
//            }
//        }
//    }
//    cout << sum.at(n - 1).at(m - 1);
//    return 0;
//}


//分组
//错误，不知原因
//#include <functional>
//#include <iostream>
//#include <utility>
//#include <vector>
//#include <map>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    long long n = 0, m = 0;
//    cin >> n >> m;
//    vector<int> v(n);
//    multimap<int, int, greater<>> mp;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    sort(v.begin(), v.end());
//    int x = 1;
//    for (int i = 1; i < n; i++)
//    {
//        if (v[i] == v[i - 1])
//        {
//            x++;
//        }
//        else
//        {
//            mp.insert(make_pair(x, v[i - 1]));
//            x = 1;
//        }
//
//        if (i == n - 1)
//        {
//            mp.insert(make_pair(x, v[i]));
//        }
//    }
//
//    if (mp.size() == m)
//    {
//        multimap<int, int>::iterator it = mp.begin();
//        cout << it->first << endl;
//    }
//    else if (mp.size() > m)
//    {
//        cout << -1 << endl;
//    }
//    else
//    {
//        while (mp.size() != m)
//        {
//            multimap<int, int>::iterator it = mp.begin();
//            int x1 = it->first / 2;
//            int x2 = it->first - x1;
//            int y = it->second;
//            mp.erase(it);
//            mp.insert(make_pair(x1, y));
//            mp.insert(make_pair(x2, y));
//        }
//        cout << mp.begin()->first << endl;
//    }
//    return 0;
//}


//过河卒

//删除相邻数字的最大分数

//最长无重复子数组

//分组

//【模板】拓扑排序

